package leetcode.tree;

import leetcode.tree.common.TreeNode;
import leetcode.tree.common.TreeUtils;

import java.util.ArrayList;
import java.util.List;

/**
 * AC O(1)空间复杂度
 */
class Solution99 {
    public void recoverTree(TreeNode root) {
        List<TreeNode> wrongNodes = new ArrayList<>();
        findWrongNodes(root, wrongNodes);
        swapNodeValues(wrongNodes);
    }

    /**
     * 交换两个指定节点中的值
     *
     * @param wrongNodes
     */
    private void swapNodeValues(List<TreeNode> wrongNodes) {
        if (wrongNodes == null || wrongNodes.size() == 0) {
            return;
        }
        int i = 0;
        int j = 1;
        if (wrongNodes.get(i) == null || wrongNodes.get(j) == null) {
            return;
        }
        int temp = wrongNodes.get(i).val;
        wrongNodes.get(i).val = wrongNodes.get(j).val;
        wrongNodes.get(j).val = temp;
    }

    /**
     * 找到两个错误的节点
     *
     * @param root
     * @param wrongNodes
     */
    private void findWrongNodes(TreeNode root, List<TreeNode> wrongNodes) {
        if (root == null) {
            return;
        }
        if (root.left == null && root.right == null) {
            return;
        }
        boolean leftFlag = TreeUtils.isAllLessThanVal(root.left, root.val);
        boolean rightFlag = TreeUtils.isAllMoreThanVal(root.right, root.val);
        // 情况一：节点交换发生在某一个子树中
        if (leftFlag == true && rightFlag == true) {
            // 递归查找左子树
            findWrongNodes(root.left, wrongNodes);
            // 递归查找右子树
            findWrongNodes(root.right, wrongNodes);
        }
        // 情况二：左右子树各有一个节点发生交换
        if (leftFlag == false && rightFlag == false) {
            // 找到左子树中比root节点大的那个
            TreeNode nodeMoreThanVal = TreeUtils.findOnlyOneNodeMoreThanVal(root.left, root.val);
            wrongNodes.add(nodeMoreThanVal);
            // 找到右子树中比root节点小的那个
            TreeNode nodeLessThanVal = TreeUtils.findOnlyOneNodeLessThanVal(root.right, root.val);
            wrongNodes.add(nodeLessThanVal);
        }

        // 情况三：节点交换发生在根节点与某个子树之间
        if ((leftFlag && rightFlag) == false && (leftFlag == true || rightFlag == true)) {
            wrongNodes.add(root);
            if (leftFlag == false) {
                // 去左子树找到第二个节点，找到子树中最大的那个节点
                TreeNode theBiggestNode = TreeUtils.findTheBiggestNodeInATree(root.left);
                wrongNodes.add(theBiggestNode);
            } else {
                // 去右子树找到第二个节点，找到子树中最小的那个节点
                TreeNode theLeastNode = TreeUtils.findTheLeastNodeInATree(root.right);
                wrongNodes.add(theLeastNode);
            }
        }
    }
}


/**
 * AC O(N)空间复杂度
 */
class Solution99_2 {
    public void recoverTree(TreeNode root) {
        List<TreeNode> treeNodeList = new ArrayList<>();
        TreeUtils.inOrderTraverseToList(root, treeNodeList);
        int i = 0;
        int j = treeNodeList.size() - 1;
        while (treeNodeList.get(i).val < treeNodeList.get(i + 1).val) {
            i++;
        }
        while (treeNodeList.get(j).val > treeNodeList.get(j - 1).val) {
            j--;
        }
        // 如果在整个二叉树节点中都找不到符合要求的值，说明二叉树本身已经是平衡二叉树了，无需调整
        if (i > treeNodeList.size() - 1 || j < 0) {
            return;
        }
        int temp = treeNodeList.get(i).val;
        treeNodeList.get(i).val = treeNodeList.get(j).val;
        treeNodeList.get(j).val = temp;
    }
}

public class leetcode99 {
    public static void main(String[] args) {

        testSolution1();

        System.out.println("==========分割线==========");

//        testSolution2();
    }

    private static void testSolution1() {
        TreeNode root = generateData();
        // 方法一
        Solution99 solution99 = new Solution99();
        solution99.recoverTree(root);

        printTree(root);
    }

    private static void printTree(TreeNode root) {
        List<TreeNode> treeNodeList = new ArrayList<>();
        TreeUtils.inOrderTraverseToList(root, treeNodeList);

        System.out.println("中序遍历============");
        treeNodeList.forEach(x -> {
            System.out.println(x.val);
        });

        System.out.println("广度遍历============");
        TreeUtils.treeBFSTraverseWithLevelInfo(root);
    }

    private static void testSolution2() {
        TreeNode root = generateData();
        // 方法二
        Solution99_2 solution99_2 = new Solution99_2();
        solution99_2.recoverTree(root);
        TreeUtils.treeBFSTraverseWithLevelInfo(root);
    }

    /**
     * 2和3需要完成交换
     *
     * @return
     */
    private static TreeNode generateData() {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(3);
        root.left.left = new TreeNode(2);
        root.left.left.left = new TreeNode(4);

        // 生成数据结果
        TreeUtils.treeBFSTraverseWithLevelInfo(root);
        return root;
    }

}
